package org.design.strategyPattern;

import java.util.Arrays;
import java.util.List;

/**
 * MergeSort
 *
 * @author 樊温军
 * @date 2025/6/24 上午11:45
 */
public class MergeSortAlgorithm implements AlgorithmStrategy{
    @Override
    public void sort(List<Integer> arr) {
        int n = arr.size();
        sort(arr, 0, n - 1);
    }


    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private void merge(List<Integer> arr, int l, int mid, int r) {

        int[] aux = Arrays.copyOfRange(arr.stream().mapToInt(Integer::intValue).toArray(), l, r + 1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 如果左半部分元素已经全部处理完毕
                arr.set(k, aux[i - l]);
                j++;
            } else if (j > r) {
                // 如果右半部分元素已经全部处理完毕
                arr.set(k, aux[i - l]);
                i++;
            } else if (aux[i - l] < aux[j - l]) {
                // 左半部分所指元素 < 右半部分所指元素
                arr.set(k, aux[i - l]);
                i++;
            } else {
                // 左半部分所指元素 >= 右半部分所指元素
                arr.set(k, aux[j - l]);
                j++;
            }
        }
    }

    // 递归使用归并排序,对arr[l...r]的范围进行排序
    private void sort(List<Integer> arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
        // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
        if (arr.get(mid) > arr.get(mid + 1)) {
            merge(arr, l, mid, r);
        }
    }

}
